package queue.Deque;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 二叉树的锯齿形层序遍历 -103
 *
 * @author yyz
 * @create 2024-01-09 14:41
 */
public class 二叉树的锯齿形层序遍历 {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(TreeNode left, int val, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();

        if (root == null) {
            return result;
        }

        Queue<TreeNode> treeNodes = new LinkedList<>();
        treeNodes.offer(root);
        int c1 = 1;
        boolean odd = true;

        while (!treeNodes.isEmpty()) {
            int c2 = 0;

            LinkedList<Integer> level = new LinkedList<>();
            for (int i = 0; i < c1; i++) {
                TreeNode poll = treeNodes.poll();

                if (odd) {
                    level.addLast(poll.val);
                } else {
                    level.addFirst(poll.val);
                }

                if (poll.left != null) {
                    treeNodes.offer(poll.left);
                    c2++;
                }
                if (poll.right != null) {
                    treeNodes.offer(poll.right);
                    c2++;
                }

            }
            odd = !odd;
            c1 = c2;
            result.add(level);
        }

        return result;
    }
    public static void main(String[] args) {
        TreeNode root = new TreeNode(
                new TreeNode(
                        new TreeNode(4),
                        2,
                        new TreeNode(5)
                ),
                1,
                new TreeNode(
                        new TreeNode(6),
                        3,
                        new TreeNode(7)
                )
        );

        List<List<Integer>> lists = new 二叉树的锯齿形层序遍历().zigzagLevelOrder(root);
        System.out.println(lists);
    }
}
